package offer2

/**
原题链接:
https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/?envType=study-plan&id=lcof&plan=lcof&plan_progress=bwt37je

leetcode官方题解
剑指 Offer 35. 复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。
在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

解释：给定的链表为空（空指针），因此返回 null。
*/

type Node35 struct {
	Val    int
	Next   *Node35
	Random *Node35
}

func copyRandomList(head *Node35) *Node35 {
	if head == nil {
		return head
	}
	p1, p2, p3 := head, head, head
	//1.
	for p1 != nil {
		tmp := &Node35{Val: p1.Val, Next: p1.Next, Random: nil}
		p1.Next = tmp
		p1 = p1.Next.Next
	}

	for p2 != nil {
		if p2.Random != nil {
			p2.Next.Random = p2.Random.Next
		}
		p2 = p2.Next.Next
	}
	// 3.
	dummy := head.Next
	tmp := dummy
	for p3 != nil {
		p3.Next = p3.Next.Next
		if p3.Next != nil {
			tmp.Next = p3.Next.Next
		}
		p3, tmp = p3.Next, tmp.Next
	}

	return dummy

}
